package com.ntd.study.algorithm.sort.impl;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.ObjectUtil;
import com.ntd.study.algorithm.sort.Sort;

import java.util.function.BiFunction;

/**
 * 快速排序
 *
 * @param <T>
 */
public class SortFast<T> implements Sort<T> {

    private BiFunction<T, T, Boolean> sort;

    public T[] quickSort(T[] arr,Integer left,Integer right) {
        right = ObjectUtil.defaultIfNull(right, arr.length - 1);
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex-1);
            quickSort(arr, partitionIndex+1, right);
        }
        return arr;
    }

    public int partition(T[] arr,Integer left,Integer right) {     // 分区操作
        // 设定基准值（pivot）
        int pivot = left,
            index = pivot + 1;
        for (var i = index; i <= right; i++) {
            if (!sort.apply(arr[i], arr[pivot])) {
                ArrayUtil.swap(arr, i, index);
                index++;
            }
        }
        ArrayUtil.swap(arr, pivot, index - 1);
        return index - 1;
    }

    @Override
    public T[] sort(T[] arrays, BiFunction<T, T, Boolean> sort) {
        this.sort = sort;
        return quickSort(arrays, 0, null);
    }

//    function partition2(arr, low, high) {
//        let pivot = arr[low];
//        while (low < high) {
//            while (low < high && arr[high] > pivot) {
//                --high;
//            }
//            arr[low] = arr[high];
//            while (low < high && arr[low] <= pivot) {
//                ++low;
//            }
//            arr[high] = arr[low];
//        }
//        arr[low] = pivot;
//        return low;
//    }
//
//    function quickSort2(arr, low, high) {
//        if (low < high) {
//            let pivot = partition2(arr, low, high);
//            quickSort2(arr, low, pivot - 1);
//            quickSort2(arr, pivot + 1, high);
//        }
//        return arr;
//    }
}
